graph

• a system of vertices and arrows
• taken to be directed
• definition: a graph \(G\) is
  • a sequence \(G := (V, A, src, tgt)\), where:
  • \(V\): the set of vertices of \(G\)
  • \(A\): the set of arrows of \(G\)
  • \(src: A \to V\): the source function for \(G\)
  • \(tgt: A \to V\): the target function for \(G\)

Categories have underlying graphs

• we have a functor: \(U: \mathbf{Cat} \to \mathbf{Grph}\)
• \((\mathbf{Ob(\mathcal{C})}, \text{Hom}_{\mathcal{C}}, dom, cod)\) is a graph
• a functor \(F: \mathcal{C} \to \mathcal{D}\) induces a graph morphism \(U(F): U(\mathcal{C}) \to U(\mathcal{D})\)